The prevalence of SONET (“Synchronous Optical Network”) technology has made the ring a popular network topology for optical networks. (SONET technology is fully familiar to those of ordinary skill in the art.) To carry a demand between two nodes on a SONET ring, traffic is routed simultaneously clockwise and counter-clockwise, one as the primary path and the other as the backup path. Often an optical network consists of a collection of a plurality of interconnected SONET rings. As is well known to those skilled in the art, a “master ring” is a ring structure which contains every node in the network (i.e., in one or more of these individual interconnected rings) exactly once, and which also respects the node ordering of every individual SONET ring. We will refer to the problem of finding such a ring, whenever it exists, as the “master ring problem” (MRP).
Mathematically, the master ring problem may be defined as follows. Suppose that a network consists of K rings, R1, . . . RK, with n1, . . . nK distinct nodes, respectively. Each ring has two possible “orientations”—clockwise and counter-clockwise. We say that R is a “sub-ring” of M (or that M is a “master ring” of R) if either the clockwise or the counter-clockwise orientation of R can be obtained from M by removing zero or more nodes from M. Specifically then, the goal of the master ring problem is to find a master ring of all of the rings in the network (e.g., R1, . . . RK) whenever it exists.
FIG. 1 shows an illustrative optical network consisting of interconnected rings. FIG. 2 shows the individual rings which make up the illustrative optical network of FIG. 1. In particular, the illustrative optical network of FIG. 1 may be separated into three individual and interconnected rings—R1, R2 and R3. (It can be seen that these rings are interconnected by virtue of the fact that each ring shares one or more nodes with another ring.) In particular, ring R1 consists of the node sequence abcdef, ring R2 consists of the node sequence achg, and ring R3 consists of the node sequence ghcdi.
FIG. 3 shows one possible example of a master ring for the illustrative optical network of FIG. 1. In particular, the example master ring shown for the illustrative network consists of the node sequence abghcdefi. It can be shown that the example master ring shown in FIG. 3 is, in fact, a master ring for the illustrative network of FIG. 1 (and shown separated into individual rings in FIG. 2), since each of the rings R1, R2, and R3 can be seen to be a sub-ring thereof. In particular, R1 is a sub-ring since its clockwise sequence abcdef is a sub-sequence of abghcdefi; R2 is a sub-ring since its clockwise sequence aghc is a sub-sequence of abghcdefi; and R3 is a sub-ring since its counter-clockwise sequence ghcdi is a sub-sequence of abghcdefi.
There are a number of reasons for finding master rings. For example, as a network evolves with growing traffic, it often expands from an initially small number of SONET rings to include a large collection of rings. Unfortunately, such expansion is often carried out in an ad-hoc manner, with circuits added and torn down over time. As a result, the network may have unnecessarily complex topology that makes network management excessively complex. One advantageous approach to solving this problem is to replace the complicated network with one of simple topology such as a master ring. Since a master ring respects the node ordering of every existing network ring, it has the advantage of preserving the routing label of every demand within an existing SONET ring. Indeed, although a demand may traverse more nodes around the master ring than around its original SONET ring, preserving the order in which the SONET nodes are traversed allows one to efficiently update the routing tables rather than redefine from scratch the Label Switched paths. (Label Switched paths are used, e.g., in Multi Protocol Label Switching, a technique familiar to those skilled in the art.) Even if the network is not intended to be rebuilt, it is still necessary that routine downtime, such as for purposes of software upgrade, can be handled. In this situation, a master ring can advantageously serve as a simple backup topology.
First, note that a master ring can be viewed as a “logical” ring—that is, neighboring nodes of the ring do not need to be physically connected by links already existing in the network. (For example, such links can be added once the master ring is defined as a new/backup topology.) In addition, note that if two SONET rings Ri and Rj intersect, then they invariably will have at least two nodes in common, since the presence of two (or more) common nodes can advantageously tolerate one node failure when supporting a demand between a node in Ri and a node in Rj.
Note also that one convenient way to represent rings is to use sequences. (See, for example, the discussion of FIGS. 1-3, above.) Each orientation of a ring with n nodes corresponds to n possible sequences, depending on the node with which the sequence begins. For example, the ring R1 in FIG. 2 has 6 clockwise sequences—abcdef, bcdefa, cdefab, defabc, efabcd, and fabcde—and 6 counter-clockwise sequences—fedcba, edcbaf, dcbafe, cbafed, bafedc, and afedcb. We also refer to each sequence as an “opening” of a ring, since the represented sequence of nodes may be thought of as being opened “between” the last node and the first node (i.e., as if the ring had the link between the last node and first node removed). Moreover, we say that S is a “sub-sequence” of T (or, equivalently, that T is a “super-sequence” of S) if S can be obtained from T by erasing zero or more symbols therefrom. Therefore, R is a “sub-ring” of M (or, equivalently M is a master ring of R) if some sequence that corresponds to R is a sub-sequence of a sequence that corresponds to M. (See, for example, FIGS. 2 and 3.)
Mathematically, the master ring problem can be shown to be “NP-hard.” (As is well known to those skilled in the art, an “NP-hard” problem is one which, in general, takes an exponential amount of time, and, therefore, cannot always be solved within the practical realities of computational limitations.) Prior art techniques for finding a master ring for a network comprising a set of interconnecting individual rings involve a “brute-force” exhaustive enumeration of essentially all possibly ways of combining the individual rings into a single (all-encompassing) ring. Such approaches can only handle relatively small instances of the master ring problem (i.e., those having a relatively small number of rings each with a relatively small number of nodes). Thus, it would be highly desirable to have a more practical method than those of the prior art for solving the master ring problem.